The present invention relates generally to optimizing complex systems, and more particularly to methods for handling constraints in a vertex based optimization of a continuous constrained complex system.
In a complex physical system, such as a power or chemical plant, various attributes, e.g., cost, profit, product, waste, quality, and efficiency, can be modeled by an objective function F(x), where x represents design (input) parameters that determine a performance (output) of the objective function. The design parameters define a search space, where each instantiation of x of the search space has a corresponding performance.
It is desired to optimize the performance of the system. This can be done by locating an optimum performance in the search space. Typically, optimization minimizes waste, and maximizes product, quality, and efficiency.
Due to engineering complexities, the design parameters may also have to conform to physically feasible limits called constraints C(x). The constraints can be dependent or independent of the objective function. For some design parameters, the performance may be infeasible.
In many complex physical systems the objective function and the constraints are non-linear, non-differentiable, and noisy. This makes it more difficult to optimize the objective function.
Formally, the optimization problem can be stated as follows. Maximize the objective function F(x) subject to constraints Ci(x)xe2x89xa70, where x is a real-valued vector of design parameters x1, x2, x3, . . . , xn for all xxcex5Rn, and i=1, . . . , m. If function minimization is required, then multiply the objective function by negative one to recast the problem to function maximization. Similarly, any constraint in the form Ci(x)xe2x89xa60 can be recast into the canonical form by multiplying Ci(x) by negative one. In the following, the terms xe2x80x9cbetter and worsexe2x80x9d performance will be used to cover both maximization and minimization problems.
FIG. 1 shows an example chemical plant 100 in simplified form. Using a cooler 101 and a heater 102, the system separates product 103 and waste 104 from an input stream 105. The system includes a condenser 106, a reboiler 107, and reactive plates 108 in a distillation or fractionating column.
The objective function F(x) 110 that models the system 100 maximizes the amount of the product (P) 113, and minimizes waste (W) 114 for a particular input stream (I) 115. The design parameters 111, vector x, can include the rate of flow in the input, the heating and cooling rates applied, the liquid and vapor compositions of each component on each plate, and the vapor pressure.
The design parameters x are subject to restrictions or interrelations, i.e., constraints C(x) 116 of many kinds. For example, compositions and flows must be positive, temperatures must not exceed certain upper bounds. More complicated constraints indicate how components interact physically. For instance, vapor and liquid compositions are related by a highly non-linear function of temperature. Careful analysis of the system 100 allows one to generate the appropriate objective function F(x) 110 and constraints C(x) 116. The function F can then be optimized to maximize product and minimize waste under particular operating conditions.
Many constrained optimization functions are solved by searching for optima in the search space using an adaptive optimization method. Often the optima lie near constraint boundaries. Consequently, avoiding search in constrained space can hinder the optimization method""s path to the optima.
The original idea for an adaptive optimization method was described by Box in xe2x80x9cEvolutionary Operation: A Method for Increasing Industrial Productivity,xe2x80x9d International Conference on Statistical Quality Control, Paris, July 1955, reproduced in Applied Statistics, VI, pp. 3-22, 1957. Box developed an idea he called xe2x80x9cevolutionary operation.xe2x80x9d Evolutionary operation pertains to an empirical optimization of full scale processes, subject to errors in observations. The basic idea is to replace the static operation of a process by a continuous and systematic scheme of slight perturbations in the control parameters. The effect of these perturbations is evaluated and the process is shifted in the direction of improvement. Box was interested in increasing production by systematically adjusting process parameters that affect output. His idea for evolutionary operation was more related to an operational procedure which a plant manager might follow than it was to optimization with a computer system.
In 1962, Spendley et al., in xe2x80x9cSequential Application of Simplex Designs in Optimization and Evolutionary Optimization,xe2x80x9d Technometrics, November 1962, applied a simplex method to the problem of non-linear numerical optimization. This simplex method should not be confused with the simplex method for linear programming.
A simplex is a geometric construct that has one more vertex than the number of dimensions in the search space. If k is the number of dimensions in the search space, then the simplex is defined by k+1 vertices in that search space. As shown in FIG. 2, a simplex in two dimensions is defined by three vertices. In one, two, and three dimensions, the simplex is respectively a line, a triangle, and a tetrahedron. In complex systems, the dimensionality of the search space can be quite large, for example, twenty or more. The lines connecting the vertices are used to visualize the simplex. They have no other function. Each vertex is a graphical representation of one of the objective function""s constraint relations and an associated performance of F(x) that determines its relative worth to the simplex.
A simplex process locates an optimum of the objective function F based on the movement of the simplex through the search space. The simplex is driven through a sequence of logical moves based on the performance evaluated as each vertex, and the orientation of the simplex. While the simplex is moved, it can adaptively change in shape as the spacing and curvature of the contours of the search space defined by the objective function F change.
As shown in FIG. 3, the basic simplex method. 300 is easy to understand and apply. The optimization begins with initial trials. The trial conditions are spread out evenly. The number of initial trials is equal to the number of design parameters plus one. The initial trials form the first simplex.
The basic simplex method has the following rules. The first rule rejects the trial with the worst performance in the current simplex. A next performance value is determined, by reflection 320 into the search space opposite the undesirable result. This next trial replaces 330 the worst trial in the simplex. This leads to a next worst performance in the simplex that, in turn, leads to another next trial, and so on. At each step, one moves away from the worst performance. By that, the simplex moves steadily towards a better performance.
The second rule never returns to the performance that has just been rejected. The calculated reflection in the search space can also produce a worst performance. Without this second rule the simplex would just oscillate between the performance values. This problem is nicely avoided by choosing the second worst performance and moving away from it.
Besides these two main rules, two additional rules are also used. Trials retained in the simplex for a specified number of steps are reevaluated 340. In the presence of noise, where identical design parameters give different performance values, the reevaluation rule avoids the simplex from getting stuck around a false worst performance. Trials never cross a constraint boundary of the search space. Instead, a very unfavorable performance is applied, forcing the simplex to move away from the constraint boundary.
A modified simplex method can adjust the shape and size of the simplex depending on the response in each step. This method is also called the variable-size simplex method. Several new rules are added to the basic simplex method rules. These new rules expand the simplex in a direction of better performance, or contract the simplex when a move was taken in a direction of worse performance. The procedures for expansion and contraction enable the modified simplex both to accelerate along a successful path of improvement and to hone in on the optimum. Therefore the modified simplex will usually reach the optimum performance quicker than with the basic method and pinpoint the optimum performance more closely.
Nelder et al., in xe2x80x9cA Simplex Method For Function Minimization,xe2x80x9d Computer Journal, Vol. 7, 1965, developed a computerized method to perform optimization using a simplex constructed of n+1 vertices to search an n-dimensional search space, also see Gill et al. in Practical Optimization, Academic Press, London, 1981.
The Nelder simplex method differs from most of the then available optimization methods because it is not based on gradients or quadratic approximations of F(x). It is an opportunistic method that assumes that an objective function is defined and that there is some optimum in the search space. The Nelder method does especially well when curvature of the search space is changing rapidly. It is relatively slower around maxima where the search space is smoother and derivative methods work faster. The Nelder method does not explicitly handle constraints. However, the method has since been adapted to handle constraints by the use of penalty functions.
The penalty function adds a penalty value to the performance of the objective function when constraints are encountered. Unfortunately, this penalty changes the actual value of the objective function and thus changes the xe2x80x9cshapexe2x80x9d of the true unconstrained search space. In effect, as further described below, the penalty function xe2x80x9cwarpsxe2x80x9d the search space near constraint boundaries. This makes it very difficult to locate an optimum near or at the boundary. Of course, in many practical systems, this is exactly where one would expect to find optimum performance. It is well known that any highly tuned system runs on its xe2x80x9cedges.xe2x80x9d
The nature of a constrained problem significantly effects the logic of the optimization process. Box, in xe2x80x9cA New Method of Constrained Optimization and Comparison With Other Methods,xe2x80x9d Computer Journal, Vol. 8, pp. 42-54, 1966, describes a xe2x80x9ccomplexxe2x80x9d method. The complex method is a modified simplex that handles constraints.
This transformation is not trivial, however, because constrained optimization is significantly different from unconstrained optimization. Therefore, in developing a constrained version of the simplex method, Box changed most of the details of the method, leaving only the basic principle of reflecting the worst of a collection of vertices. In the new process, constraints are evaluated and dealt with differently than they are in methods using penalty functions.
Instead of using a penalty function, Box uses a constrained performance that is separate from the objective function itself. The constrained performance has a different functional meaning or value than the unconstrained performance. However, the constrained performance can be optimized just the same.
Box defines a constraint whose boundary is easily identified (e.g., x2xe2x89xa77) and whose evaluation is independent of the objective function F an independent or explicit constraint. In contrast, a dependent or implicit constraint has a complex boundary and requires an evaluation of F. Box attempts to stay very close to a constraint boundary by setting independent parameter violations just inside the constraint limit. If a dependent constraint is violated, the test vertex is moved xc2xd way towards the centroid. From his results, Box concludes that xe2x80x9cin constraint bound problems, the constraints are of as much importance as the contours and gradient of the objective function.xe2x80x9d
One problem with the prior art simplex and complex methods is that they tend to lose dimensionality due to concentrating on the vertex with the worst performance. This tendency for the vertices to xe2x80x9cline-outxe2x80x9d reduces their ability to move about the search space.
Therefore, it is desired to provide an optimization method that is able to operate without losing dimensionality. Furthermore, the method should be able to locate optima near a constraint boundary. In addition, the method should be applicable to global optimization problems where many local optima exist, and the method should be able to adapt to dynamically changing environments, for example, in a real time control system.
Provided is an optimization method that, unlike those of the prior art, utilizes a constrained space to help locate an optimum. The rationale for this implementation is that many optima lie near constraint boundaries. The strict avoidance of constrained space, as in the prior art, can hinder a search for the optimum. In the present method, vertices of a set are allowed, and sometimes encouraged, to move into the constrained space, unlike the methods of the prior art, where constraint violations are prohibited or severely penalized.
A discontinuity at a constraint boundary is handled by partitioning the performances of the search space into any number of unique levels. The partitioning is done by grouping the constraints into one or more hierarchical levels. Each vertex is then evaluated according to the group of constraints in each level, beginning with the lowest level. If the vertex evaluates to a negative performance, than the first level and its negative performance is assigned to the vertex. If not, then the vertex is evaluated at the next level, and so forth. Only if the vertex still has a non-negative performance after all levels of constraints have been considered is the objective function evaluated. This effectively partitions the search space into a plurality of levels.
The manner of partitioning differs from Box""s explicit-implicit categorization. The present method defines a constrained performance for each level of constraints that is independent of a feasible objective function. Furthermore, the grouping of the constraints can dynamically be changed during the search for the optimum performance.
The constrained performance for a particular level of constraints is some combination of the violated constraints in that level, for example, the sum. A constraint is considered violated when its value is strictly less than zero. Therefore, by definition, the sum of the violated constraints is negative and will be maximized towards the positive or feasible direction.
In conjunction with the multiple levels of performances, the present method defines a set of rules concerning the ordering and movement of the set of vertices as they straddle a constraint boundary. These rules and the multiple levels of constrained performances make the present method less sensitive to constraint discontinuities, and can significantly aid motion along a constraint boundary toward an optimum.
In addition to the new constraint handling techniques, the method is improved so that loss of dimensionality is reduced. One problem with the adaptive simplex process of the prior art is that it tends to lose width in one spatial dimension. This loss of dimensionality then restricts motion in that direction. The present method attempts to move every vertex before resorting the set of vertices. Both the simplex and complex methods of the prior art concentrate exclusively on the present worst performance vertex.
More particularly, provided is a method that optimizes a system. Performances of a plurality of design parameters of an objective function modeling the system are represented in a search space. A set of vertices are positioned in the search space, and each vertex has an associated performance. The model also includes a plurality of constraints. The constraints and the objective function are grouped according to a plurality of unique hierarchical levels. The group including the objective function has a highest level. The performance of a particular vertex is evaluated, in a low to high order of the levels, according to the:groupings of the constraints and the objective function. The evaluated performance and the associated level is assigned to the particular vertex as soon as the evaluated performance is negative, unless the associated level is the highest level, in which case the assigned performance is evaluated from the objective function to partition the search space into a plurality of partitions according to the levels.